package io.tec.cloud.algorithm.c02_v20220606;

import java.util.HashMap;
import java.util.Map;

/**
 *
 */
public class C02_Code02_EvenTimesOddTimes {

    /**
     * 一个数组中出现了奇数次的数
     *
     * @param nums
     * @return
     */
    public static int printOddTimesNum1(int[] nums) {
        int result = 0;
        for (int n : nums) {
            result ^= n;
        }
        return result;
    }

    /**
     * arr中，有两种数，出现奇数次
     *
     * @param nums
     * @return
     */
    public static int[] printOddTimesNum2(int[] nums) {
        int eor = 0;
        for (int n : nums) {
            eor ^= n;
        }

        int rightOne = eor & ((~eor) + 1);

        int x = 0;
        int y = 0;
        for (int n : nums) {
            if ((n & rightOne) == 0) {
                x ^= n;
            } else {
                y ^= n;
            }
        }
//        System.out.println("x=" + x + ", y=" + (eor ^ x));
//        return new int[]{x, eor ^ x};
        return new int[]{x, y};
    }


    public static void main(String[] args) {
        test2();
    }

    public static void test1() {
        int testTimes = 1000000;
        int maxLength = 10;
        int maxValue = 500;
        for (int t = 0; t < testTimes; t++) {
            int[] original = generateOneNumEvenTimesArray(maxLength, maxValue);
            int r1 = printOddTimesNum1(original);
            int r2 = testPrintOddTimesNum1(original);
            if (r1 != r2) {
                p(original);
                System.out.println("error");
                return;
            }
        }

        System.out.println("finish");
    }

    public static void test2() {
        int testTimes = 1000000;
        int maxLength = 5;
        int maxValue = 500;
        for (int t = 0; t < testTimes; t++) {
            int[] original = generateTwoNumEvenTimesArray(maxLength, maxValue);
            int[] r1 = printOddTimesNum2(original);
            int[] r2 = testPrintOddTimesNum2(original);
            if (!((r1[0] + r1[1] == r2[0] + r2[1]) && (r1[0] == r2[0] || r1[0] == r2[1]))) {
                p(original);
                System.out.println("error");
                return;
            }
        }

        System.out.println("finish");
    }

    public static void p(int[] arr) {
        for (int item : arr) {
            System.out.print(item + " ,");
        }
        System.out.println();
    }

    private static int[] generateTwoNumEvenTimesArray(int maxLength, int maxValue) {
        int evenTime1 = (int) (Math.random() * maxLength + 1);
        evenTime1 = evenTime1 % 2 == 0 ? evenTime1++ : evenTime1;
        if (evenTime1 % 2 == 0) {
            evenTime1++;
        }
        int evenNum1 = (int) (Math.random() * maxValue);


        int evenTime2 = (int) (Math.random() * maxLength + 1);
        if (evenTime2 % 2 == 0) {
            evenTime2++;
        }
        int evenNum2 = (int) (Math.random() * maxValue);

        int length = evenTime1 + evenTime2 + (int) ((Math.random() * maxLength + 1)) * maxLength * 2;
        int[] arr = new int[length];
        int i = 0;
        for (; i < evenTime1 + evenTime2; ) {
            arr[i++] = evenNum1;
            arr[i++] = evenNum2;
        }

        for (; i < length; ) {
            int odd = (int) (Math.random() * (length - evenTime1 - evenTime2)) + 1;
            if (odd % 2 != 0) {
                odd--;
            }
            int oddNum = ((int) (Math.random() * maxLength + 1)) * 2;
            for (int j = 0; j < odd; j++) {
                if (i + 1 <= length) {
                    arr[i++] = oddNum;
                } else {
                    i++;
                }
            }
        }

        for (int idx = 0; idx < arr.length; idx++) {
            int randomIndex = (int) (Math.random() * arr.length);
            int tmp = arr[randomIndex];
            arr[randomIndex] = arr[idx];
            arr[idx] = tmp;
        }

        return arr;
    }

    private static int[] generateOneNumEvenTimesArray(int maxLength, int maxValue) {
        int target = (int) (Math.random() * maxValue - Math.random() * maxValue);
        int times = (int) (Math.random() * maxLength) + 1;
        if (times % 2 == 0) {
            times++;
        }

        int length = times + ((int) (Math.random() * maxLength) + 1) * 2;
        int[] arr = new int[length];
        int i = 0;
        for (; i < times; i++) {
            arr[i] = target;
        }
        for (; i < length; ) {
            int randomValue = (int) (Math.random() * maxValue - Math.random() * maxValue);
            arr[i++] = randomValue;
            arr[i++] = randomValue;
        }

        for (int idx = 0; idx < arr.length; idx++) {
            int randomIndex = (int) (Math.random() * arr.length);
            int tmp = arr[randomIndex];
            arr[randomIndex] = arr[idx];
            arr[idx] = tmp;
        }

        return arr;
    }

    public static Integer testPrintOddTimesNum1(int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int item : arr) {
            if (map.containsKey(item)) {
                map.put(item, map.get(item) + 1);
            } else {
                map.put(item, 1);
            }
        }
        for (Integer key : map.keySet()) {
            if (map.get(key) % 2 != 0) {
                return key;
            }
        }
        return null;
    }

    public static int[] testPrintOddTimesNum2(int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int item : arr) {
            if (map.containsKey(item)) {
                map.put(item, map.get(item) + 1);
            } else {
                map.put(item, 1);
            }
        }
        int[] result = new int[2];
        int idx = 0;
        for (Integer key : map.keySet()) {
            if (map.get(key) % 2 != 0) {
                result[idx++] = key;
            }
        }
        return result;
    }
}
